#include<stdlib.h>
#include <stdio.h>
#include "ArrayList.h"

// 验证数据是否正常
int verificationArrayList(ArrayList *arrayList) {
    return arrayList != NULL && arrayList->dataLength > 0;
}

// 初始化顺序表
void initArrayList(ArrayList *arrayList, int size) {
    if (size == 0) {
        size = ArrayListMaxSize;
    }
    arrayList->dataLength = size;
    arrayList->data = malloc(sizeof(ElemType) * size);
    arrayList->size = 0;
}

// 尾插入元素
int addArrayList(ArrayList *arrayList, ElemType e) {
    if (verificationArrayList(arrayList)) {
        // 判断当前长度是小于容量
        if (arrayList->size < arrayList->dataLength) {
            arrayList->data[arrayList->size++] = e;
            return 1;
        }
    }
    return 0;
}


// 一个顺序表追加到另一个顺序表
int addAllArrayList(ArrayList *arrayList, ArrayList *al) {
    if (verificationArrayList(arrayList) && al != NULL && al->size > 0) {
        // 添加元素的个数
        int count;
        if ((arrayList->size + al->size) <= arrayList->dataLength) {
            count = al->size;
        } else {
            count = arrayList->dataLength - arrayList->size;
        }
        for (int i = 0; i < count; i++) {
            arrayList->data[arrayList->size++] = al->data[i];
        }
        return count;
    }
    return 0;
}

// 在给定位置插入元素
int addIndexArrayList(ArrayList *arrayList, int index, ElemType e) {
    if (verificationArrayList(arrayList) && index < arrayList->dataLength) {
        if (arrayList->size < arrayList->dataLength) {
            arrayList->size++;
        }
        // index后面的元素往后移动
        for (int i = arrayList->size - 1; i > index; i--) {
            arrayList->data[i] = arrayList->data[i - 1];
        }
        arrayList->data[index] = e;
        return 1;
    }
    return 0;
}


// 输出顺序表
void showArrayList(ArrayList *arrayList) {
    if (verificationArrayList(arrayList)) {
        printf("长度：%d ==> [", arrayList->size);
        for (int i = 0; i < arrayList->size; ++i) {
            printf("'%c'", arrayList->data[i]);
            if (i == arrayList->size - 1) {
                printf("]\n");
            } else {
                printf(",");
            }

        }
    }
}


// 顺序表长度
int arrayListLength(ArrayList *arrayList) {
    if (verificationArrayList(arrayList)) {
        return arrayList->size;
    }
    return 0;
}

// 判断顺序表是否为空
int isEmptyArrayList(ArrayList *arrayList) {
    int size = 0;
    if (verificationArrayList(arrayList)) {
        size = arrayList->size;
    }
    return size == 0;
}

// 顺序表给定位置的元素
ElemType getElemTypeArrayList(ArrayList *arrayList, int index) {
    if (verificationArrayList(arrayList) && arrayList->size > index) {
        return arrayList->data[index];
    }
    ElemType elemtype = 0;
    return elemtype;
}

// 输出给定元素的位置
int getIndexArrayList(ArrayList *arrayList, ElemType e) {
    int index = -1;
    if (verificationArrayList(arrayList)) {
        for (int i = 0; i < arrayList->size; ++i) {
            if (arrayList->data[i] == e) {
                index = i;
                break;
            }
        }
    }
    return index;
}


// 删除顺序表，释放内存
void deleteArrayList(ArrayList *arrayList) {
    if (verificationArrayList(arrayList)) {
        free(arrayList->data);
        // 释放后置为null
        arrayList->data = NULL;
        arrayList->size = arrayList->dataLength = 0;
    }
}

/*
 * 以第一个元素为分界线，将所有小于它的元素移到该元素的前面，大于它的元素移到该元素的后面
 */
void move(ArrayList *arrayList) {
    int i = 0, j = arrayList->size - 1;
    ElemType pivot = arrayList->data[0];
    while (i != j) {
        // 右边查找小于pivot值, 直接覆盖i的值
        while (j > i && pivot <= arrayList->data[j]) {
            j--;
        }
        arrayList->data[i] = arrayList->data[j];
        // 左边查找大于pivot值, 直接覆盖j的值
        while (i < j && pivot >= arrayList->data[i]) {
            i++;
        }
        arrayList->data[j] = arrayList->data[i];
    }
    arrayList->data[i] = pivot;
}

// 测试
void arrayListTest() {
    ArrayList *arrayList = malloc(sizeof *arrayList);
    initArrayList(arrayList, 6);
    if (isEmptyArrayList(arrayList)) {
        printf("arrayList为空\n");
    }
    ElemType a = 'a', b = 'b', c = 'c', d = 'd', e = 'e';
    addArrayList(arrayList, a);
    ArrayList *al1 = malloc(sizeof *al1);
    initArrayList(al1, 12);
    addArrayList(al1, b);
    addArrayList(al1, c);
    addArrayList(al1, d);
    addArrayList(al1, e);
    printf("arrayList = ");
    showArrayList(arrayList);
    printf("al1 = ");
    showArrayList(al1);
    addAllArrayList(arrayList, al1);
    printf("arrayList = ");
    showArrayList(arrayList);

    printf("输出位置为4的元素是%c\n", getElemTypeArrayList(arrayList, 4));

    printf("输出c的位置%d\n", getIndexArrayList(arrayList, 'c'));

    printf("顺序表的长度%d", arrayListLength(arrayList));

    addIndexArrayList(arrayList, 2, 'o');
    showArrayList(arrayList);


    printf("\n======================我是分割线===========================\n");
    ArrayList *al2 = malloc(sizeof *al2);
    initArrayList(al2, 10);
    addArrayList(al2, '3');
    addArrayList(al2, '5');
    addArrayList(al2, '6');
    addArrayList(al2, '1');
    addArrayList(al2, '4');
    addArrayList(al2, '2');
    addArrayList(al2, '7');
    addArrayList(al2, '9');
    addArrayList(al2, '8');
    addArrayList(al2, '0');
    printf("执行前:");
    showArrayList(al2);
    move(al2);
    printf("执行后:");
    showArrayList(al2);

    deleteArrayList(al2);
    deleteArrayList(al1);
    deleteArrayList(arrayList);
    free(al2);
    al2 = NULL;
    free(al1);
    al1 = NULL;
    free(arrayList);
    arrayList = NULL;
}


